package day003;

public class Code05_isBalancedTree {

    public static class Node{
        public int value;
        public Node left;
        public Node right;

        public Node(int value) {
            this.value = value;
        }

        public Node(int value, Node left, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
    public static boolean isBalanced(Node head){
        if(head == null){
            return true;
        }
        return process(head).isBt;
    }

    public static ReturnData process(Node x){
        if(x == null){
            return new ReturnData(true, 0);
        }
        ReturnData lData = process(x.left);
        ReturnData rData = process(x.right);


        boolean isBt = true;
        int height = Math.max(lData.height , rData.height) + 1;
        if((!lData.isBt || !rData.isBt) || Math.abs(lData.height - rData.height) >=2){
            isBt = false;
        }
        //isBt = lData.isBt && rData.isBt && Math.abs(lData.height - rData.height) <2;
        return new ReturnData(isBt, height);


    }
    public static class ReturnData{
        public boolean isBt;
        public int height;

        public ReturnData(boolean isBt, int height) {
            this.isBt = isBt;
            this.height = height;
        }
    }

    public static void main(String[] args) {
        Node n16 = new Node(16);
        Node n17 = new Node(17, n16, null);
        Node n15 = new Node(15,null, n17);
        Node n19 = new Node(19);
        Node n18 = new Node(18, n15, n19);
        Node n2 = new Node(2);
        Node n9 = new Node(9);
        Node n5 = new Node(5, n2, n9);
        Node n12 = new Node(12, n5, n18);

        System.out.println(isBalanced(n12));

    }
}
